class Solution:
    def maxProduct(self, s: str) -> int:
        # ---------- 寻找所有回文子序列 ----------
        # 最多 2 * 12 = 4096个子序列
        size1 = len(s)
        strings = []
        for stat in range(1, (1 << size1)):
            lst = [i for i in range(size1) if 1 << i & stat]
            left, right = 0, len(lst) - 1
            while left < right:
                if s[lst[left]] == s[lst[right]]:
                    left += 1
                    right -= 1
                else:
                    break
            if left >= right:
                strings.append([len(lst), stat])

        strings.sort(key=lambda x: x[0], reverse=True)

        # 寻找最终结果
        size2 = len(strings)
        ans = 1
        for i in range(size2):
            len1, stat1 = strings[i]
            if len1 * len1 < ans:
                break
            for j in range(i, size2):
                len2, stat2 = strings[j]
                if len1 * len2 < ans:
                    break
                if not stat1 & stat2:
                    ans = len1 * len2
        return ans


if __name__ == "__main__":
    print(Solution().maxProduct(s="leetcodecom"))  # 9
    print(Solution().maxProduct(s="bb"))  # 1
    print(Solution().maxProduct(s="accbcaxxcxx"))  # 25

    # 自制用例
    print(Solution().maxProduct(s="aaaaaaaaaaaa"))  # 36
